using System;
using System.Collections.Generic;

namespace LannyPractiseCode
{
    /// <summary>
    /// 排序算法
    /// </summary>
    public class SortHelper
    {

        #region 冒泡排序
        /// <summary>
        /// 冒泡方法一
        /// </summary>
        /// <param name="arrList"></param>
        /// 时间复杂度：O（n^2）
        public static void BubbleSort1(List<int> arrList)
        {
            //第一层循环： 表明要比较的次数，比如arrList.count个数，肯定要比较count-1次
            for (int i = 0; i < arrList.Count; i++)
            {
                //arrList.count-1：取数据最后一个数下标，
                //j>i: 从后往前的的下标一定大于从前往后的下标，否则就超越了。           
                for (int j = arrList.Count - 1; j > i; j--)
                {
                    if (arrList[j - 1] > arrList[j])//如果前面一个数大于后面一个数则交换
                    {
                        int temp = arrList[j - 1];
                        arrList[j - 1] = arrList[j];
                        arrList[j] = temp;
                    }
                }
                //System.Console.WriteLine("第a【" + i + "】趟排序");
                //Console.WriteLine(string.Join(",", arrList));
            }

            //System.Console.WriteLine("排序结果：");
            //Console.WriteLine(string.Join(",", arrList));
        }

        /// <summary>
        /// 冒泡方法二，每次把最大的放到最后面
        /// </summary>
        /// <param name="arrList"></param>
        public static void BubbleSort2(List<int> arrList)
        {
            bool flag = false;//表示是否进行交换,优化 优化
            for (int i = 0; i < arrList.Count; i++)
            {
                for (int j = 0; j < arrList.Count - 1 - i; j++)
                {
                    if (arrList[j] > arrList[j + 1])
                    {
                        flag = true;
                        int temp = arrList[j];
                        arrList[j] = arrList[j + 1];
                        arrList[j + 1] = temp;
                    }
                }
                if (!flag)//在一趟排序中，一次交换都没有发生过。
                    break;
                else
                    flag = false;
                //System.Console.WriteLine("第a【" + i + "】趟排序");
                //Console.WriteLine(string.Join(",", arrList));
            }
            //System.Console.WriteLine("排序结果：");
            //Console.WriteLine(string.Join(",", arrList));
        }
        #endregion

        #region 插入排序
        /// <summary>
        /// 插入排序
        /// </summary>
        /// <param name="arrList"></param>
        public static void InsertSort(List<int> arrList)
        {
            int temp;
            for (int i = 1; i < arrList.Count; i++)
            {
                temp = arrList[i];
                for (int j = i - 1; j >= 0 && arrList[j] > arrList[j + 1]; j--)
                {
                    temp = arrList[j];
                    arrList[j] = arrList[j + 1];
                    arrList[j + 1] = temp;
                }
                
            }
        }
        #endregion
        
        #region 快速排序
        public static int Division(List<int> list, int left, int right)
        {
            int baseNum = list[left]; //首先挑选一个基准元素
            while (left < right)
            {
                //从数组的右端开始向前找，一直找到比base小的数字为止(包括base同等数)
                while (left < right && list[right] >= baseNum)
                    right = right - 1;

                //最终找到了比baseNum小的元素，要做的事情就是此元素放到base的位置
                list[left] = list[right];

                //从数组的左端开始向后找，一直找到比base大的数字为止（包括base同等数）
                while (left < right && list[left] <= baseNum)
                    left = left + 1;

                //最终找到了比baseNum大的元素，要做的事情就是将此元素放到最后的位置
                list[right] = list[left];
            }
            list[left] = baseNum;
            //执行完一次操作
            //最后就是把baseNum放到该left的位置
            //最终，left位置的左侧数值部分比left小，left位置右侧数值比left大
            return left;
        }

        public static void QuickSort(List<int> list, int left, int right)
        {
            //左下标一定小于右下标，否则就超越了
            if (left < right)
            {
                //对数组进行分割，取出下次分割的基准标号
                int i = Division(list, left, right);
                //对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
                QuickSort(list, left, i - 1);
                //对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
                QuickSort(list, i + 1, right);
            }
        }
        #endregion

        #region 选择排序
        /// <summary>
        /// 选择排序
        /// </summary>
        /// <param name="arrLists"></param>
        public static void SelectSort(List<int> arrLists)
        {
            for (int i = 0; i < arrLists.Count; i++)//要遍历的次数
            {
                int minIndex = i;  //假象minIndex的下标值最小
                for (int j = i + 1; j < arrLists.Count; j++)
                {
                    if (arrLists[j] < arrLists[minIndex]) //如果minIndex下标的值大于j下标的值,则记录较小值下标j
                        minIndex = j;
                }
                //最后将假想最小值跟真的最小值进行交换
                int tempData = arrLists[i];
                arrLists[i] = arrLists[minIndex];
                arrLists[minIndex] = tempData;
            }
            Console.WriteLine(string.Join(",", arrLists));
        }
        #endregion

        #region 希尔排序
        /// <summary>
        /// 希尔排序
        /// </summary>
        /// <param name="arrLists"></param>
        public static void ShellSort(List<int> arrLists)
        {
            int step = arrLists.Count / 2;//取增量
            while (step >= 1)
            {
                for (int i = step; i < arrLists.Count; i++) //无序系列
                {
                    var temp = arrLists[i];
                    int j;
                    for (j = i - step; j >= 0 && temp < arrLists[j]; j = j - step)  //有序系列
                    {
                        arrLists[j + step] = arrLists[j];
                    }
                    arrLists[j + step] = temp;
                }
                step = step / 2;
            }
            Console.WriteLine(string.Join(",", arrLists));
        }
        #endregion

        #region 堆排序
        ///<summary>
        /// 构建堆
        ///</summary>
        ///<param name="list">待排序的集合</param>
        ///<param name="parent">父节点</param>
        ///<param name="length">输出根堆时剔除最大值使用</param>
        static void HeapAdjust(List<int> list, int parent, int length)
        {
            //temp保存当前父节点
            int temp = list[parent];
            //得到左孩子(这可是二叉树的定义，大家看图也可知道)
            int child = 2 * parent + 1;
            while (child < length)
            {
                //如果parent有右孩子，则要判断左孩子是否小于右孩子
                if (child + 1 < length && list[child] < list[child + 1])
                    child++;
                //父亲节点大于子节点，就不用做交换
                if (temp >= list[child])
                    break;
                //将较大子节点的值赋给父亲节点
                list[parent] = list[child];
                //然后将子节点做为父亲节点，已防止是否破坏根堆时重新构造
                parent = child;
                //找到该父亲节点较小的左孩子节点
                child = 2 * parent + 1;
            }
            //最后将temp值赋给较大的子节点，以形成两值交换
            list[parent] = temp;
        }

        ///<summary>
        /// 堆排序
        ///</summary>
        ///<param name="list"></param>
        public static void HeapSort(List<int> list)
        {
            //list.Count/2-1:就是堆中父节点的个数
            for (int i = list.Count / 2 - 1; i >= 0; i--)
            {
                HeapAdjust(list, i, list.Count);
            }
            //最后输出堆元素
            for (int i = list.Count - 1; i > 0; i--)
            {
                //堆顶与当前堆的第i个元素进行值对调
                int temp = list[0];
                list[0] = list[i];
                list[i] = temp;
                //因为两值交换，可能破坏根堆，所以必须重新构造
                HeapAdjust(list, 0, i);
            }
        }
        #endregion

        #region  归并排序
        private static void Merge(int[] arr, int left, int mid, int right)
        {
            //System.Console.WriteLine("Left:="+left +",right="+right);
            int[] temp = new int[right - left + 1];
            int i = left;//左序列指针，左边有序系列的初始索引
            int j = mid + 1;//右序列指针，右边有序系列的初始索引
            int t = 0;//指向temp的当前索引
            //先把左右两边（有序）的数据按照规则填充到temp数据
            //直到左右两边的有序序列，有一边处理完毕为止。
            while (i <= mid && j <= right)
            {
                //如果左边的有序序列的当前元素，小于等于右边的有序序列的当前元素
                //即将左边的当前元素，填充到temp数组
                //然后 t++ ，i++
                if (arr[i] < arr[j])
                {
                    temp[t++] = arr[i++];
                }
                else//反之，将右边有序序列的当前元素，填充到temp数组
                {
                    temp[t++] = arr[j++];
                }
            }
            while (i <= mid) //将左边剩余元素填充进temp中
            {
                temp[t++] = arr[i++];
            }
            while (j <= right) //将右序列剩余元素填充进temp中
            {
                temp[t++] = arr[j++];
            }
            for (int k2 = 0; k2 < temp.Length; k2++)
            {
                arr[k2 + left] = temp[k2];
            }
            //System.Console.WriteLine("****"+string.Join(',',arr));
        }

        public static void MergeSort(int[] arrLists, int left, int right)
        {
            int mid = (left + right) / 2;
            if (left < right)
            {
                //左边归并排序，使得左子序列有序
                MergeSort(arrLists, left, mid);
                //右边归并排序，使得右子序列有序
                MergeSort(arrLists, mid + 1, right);
                //将两个有序子数组合并操作
                Merge(arrLists, left, mid, right);
                //System.Console.WriteLine(string.Join(',', arrLists));
            }
        }

        #endregion
    }
}